Solid modeling is a known technique for modeling objects with a computer and for specifying a design and a manufacturing process of such objects. A method for interactively creating, displaying, and manipulating solid models is required to make efficient use of the descriptive power of solid modeling. Methods for the fast display of solids described by Constructive Solid Geometry (CSG), using multiple z-buffers, have been previously described. By example, in commonly assigned U.S. Pat. No. 5,027,292, issued Jun. 25, 1991, entitled "Multiple Depth Buffers for Graphics and Solid Modelling" by J. Rossignac et al., there is described the use of front and back z-buffers.
Another important consideration for displaying solids is an ability to selectively display only certain parts of the solids. These parts are defined by specifying a subspace of the entire screen space, or by defining a cross-section of the solid. Typically, these subspaces are delimited by planes, referred to in the art as clipping planes. The cross-section may be defined as the intersection of the solid with the clipping plane. Efficient clipping operations provide several valuable interactive operations.
First, the use of a clipping plane or clipping planes clarifies the image by clipping away, or visually removing, portions of the solid that are not of interest to a user.
Second, the use of a clipping plane or clipping planes enables the user to view the interior structure of a solid by clipping away those portions of the solid that enclose an interior region of interest.
Third, the use of a clipping plane enables the user to gain an understanding of the shape of complex solids by inspecting various cross-sections that are defined by appropriate positioning of the clipping plane or clipping planes.
Displaying clipped solids should ideally result in images that are as close to the intended operation, namely cross-sectioning the solid, as possible. Therefore, it is desirable that the image of the interior of an object be easily identified on the display. Also, the user benefits most from the clipping operation if it is accomplished interactively, i.e. a change in the position of the clipping plane is reflected in the image with little latency. Therefore, it is desirable that clipping be implemented with relatively simple logical and arithmetic operations that can be readily performed by, or supported by, hardware.
Many traditional surface clipping techniques discard those portions of the faces of the solid that lie outside of the clipping volume. As a result, the backface(s) of the solid are displayed at those pixels where the front surface(s) have been clipped away. However, this is undesirable because it does not reflect the reality that solids are partially or entirely filled with material.
Traditionally, the clipping of solids has been accomplished with clipping polygons that bound the solid. Several techniques for polygon clipping are known. By example, Sutherland and Hodgman describe in "Reentrant Polygon Clipping" CACM, 18(1), pp. 32-42, January 1974, a technique that clips an arbitrary connected polygon against convex clipping regions or a convex clipping volume. This technique successively clips each polygon against each of the clipping planes. During this process a new polygon is generated whose vertices lie inside of, or on, the boundary of the clipping volume. Portions of the original polygon that are outside of the clipping volume are discarded.
Liang and Barsky describe in "An Analysis and Algorithm for Polygon Clipping" CACM 26(11), November 1983 (Corrigendum, CACM, 27(2)), February 1984, a more efficient technique for clipping polygons against a rectangular clipping window, These authors reduce the computational effort by determining which sides of a rectangle might be intersected by an edge of the polygon to be clipped. Again, regions outside of the clipping rectangle are removed from the data structure by generating a new polygon having vertices that are contained in the clipping rectangle.
Weiler describes in "Polygon Comparison Using a Graph Representation", SIGGRAPH '80, a method to clip a polygon against another arbitrary polygon. The technique divides the supporting plain of the polygons into portions that are covered by none, one, or both polygons. The method selects those portions that are covered by both polygons. The other portions are discarded.
As is evident, a common property of all of these techniques is that portions of the polygon outside the clipping volume are removed. When these polygons bound a solid, clipping against the front faces reveals the interior of the volume of the solid and displays the back faces, as seen in FIG. 2a and FIG. 2b. In that both the front faces and the back faces would be subject to the same lighting calculations, such an image may be visually confusing.
What is required instead, when a front of a solid is clipped by a front clipping plane, is to provide a visual effect of a cross-section through the solid. By example, the intersection of the front clipping plane and the solid should be displayed in, by example only, a constant color and/or a cross-hatched pattern. This approach would more accurately model the reality that a solid is not empty space bounded by surfaces, but contains visually distinct material.
It is thus one object of the invention to provide a clipping technique that detects those pixels that project onto a region where the interior of a cross-sectional solid is displayed so as to render these pixels in a visually distinct manner. By example, interior pixels may be flat shaded while surface pixels are rendered, taking into account the scene illumination.
It is a further object of the invention to provide for a correct rendering of solid objects by the use of a plurality of depth buffers, in conjunction with a pixel parity flag memory plane, so as to detect and make visually apparent interior material that is exposed by one or more clipping planes or surfaces that intersect a solid object.